package com.itheima.datastructure.linkedlist;

/**
 * 判断回文链表 如果一个链表正序和倒序都一样，那么这个链表就是一个回文链表
 */
public class E09Leetcode234 {
    /*
        步骤1. 找中间点的同时反转前半个链表
        步骤2. 反转后的前半个链表 与 中间点开始的后半个链表 逐一比较
                p1      p2
        1   2   2   1   null

        n1
        2   1

     */
    public boolean isPalindrome(ListNode head) {
        ListNode p1 = head; // 慢（就是middle）
        ListNode p2 = head; // 快
        ListNode n1 = null; // 新头
        ListNode o1 = head; // 旧头
        while (p2 != null && p2.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;

            // 反转链表
            ListNode o2 = o1.next;
            o1.next = n1;
            n1 = o1;
            o1 = o2;

            // 反转链表
//            o1.next = n1;
//            n1 = o1;
//            o1 = p1;
        }
        System.out.println(n1);
        System.out.println(p1);

        if (p2 != null) { // 奇数节点
            p1 = p1.next;
        }

        while (n1 != null) {
            if (n1.val != p1.val) {
                return false;
            }
            n1 = n1.next;
            p1 = p1.next;
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(new E09Leetcode234()
                .isPalindrome(ListNode.of(1, 2, 2, 1)));
        System.out.println(new E09Leetcode234()
                .isPalindrome(ListNode.of(1, 2, 3, 2, 1)));
    }

    /*
                p1
                        p2
        1   2   3   2   1   null

        n1
        2   1
     */

    public boolean isPalindrome01(ListNode head) {
        //找中间节点
        ListNode middleNode = middleNode(head);
        //翻转后半部分
        ListNode newHead = reverseList(middleNode);


        //遍历比较
        while (newHead != null) {
            if (newHead.val != head.val) {
                return false;
            }
            newHead = newHead.next;
            head = head.next;
        }
        return true;

    }


    /**
     * 找到中间节点
     *
     * @param head 头节点
     * @return 中间节点
     * @return
     */
    private ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    //反转链表
    private ListNode reverseList(ListNode o1) {
        ListNode n1 = null;

        while (o1 != null) {
            //记录下一个节点
            ListNode o2 = o1.next;
            //添加到新链表头部(o1成为头节点)
            o1.next = n1;
            //更新n1
            n1 = o1;
            //移动
            o1 = o2;
        }
        return n1;


    }

}
